package test.n00500;


import java.util.ArrayList;
import java.util.List;

import static utils.Tools.listOf;

public class Problem00570 {
    public static void main(String[] args) {
        println(new int[][]{
                {1, 4}, {6, 9}
        }, new int[]{2, 5});
    }

    public static void println(int[][] intervals, int[] newInterval) {
        Solution ss = new Solution();
        System.out.println(listOf(intervals) + "," + listOf(newInterval) + "," + listOf(ss.insert(intervals, newInterval)));
    }

    public static class Solution {

        /**
         * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
         * <p>
         * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）
         *
         * @param intervals
         * @param newInterval
         * @return
         */
        public int[][] insert(int[][] intervals, int[] newInterval) {
            if (intervals.length == 0) {
                return new int[][]{
                        newInterval
                };
            }
            List<int[]> result = new ArrayList<>();
            int left = newInterval[0], right = newInterval[1];
            boolean placed = false;
            for (int i = 0; i < intervals.length; i++) {
                if (intervals[i][0] > right) {
                    if (!placed) {
                        result.add(new int[]{left, right});
                        placed = true;
                    }
                    result.add(intervals[i]);
                } else if (intervals[i][1] < left) {
                    result.add(intervals[i]);
                } else {
                    left = Math.min(left, intervals[i][0]);
                    right = Math.max(right, intervals[i][1]);
                }
            }

            if (!placed) {
                result.add(new int[]{left, right});
            }
            return result.toArray(new int[0][]);
        }
    }
}
